//package leetcode;
//
//class Node {
//    public int val;
//    public Node left;
//    public Node right;
//
//    public Node() {
//
//    }
//
//    public Node(int val) {
//        this.val = val;
//    }
//
//    public Node(int val, Node left, Node right) {
//        this.val = val;
//        this.left = left;
//        this.right = right;
//    }
//}
//
//class Solution {
//    Node pre = null;
//    Node head = null;
//
//    public Node treeToDoublyList(Node root) {
//        if (root == null) {
//            return null;
//        }
//        dfs(root);
//        head.left = pre;
//        pre.right = head;
//        return head;
//    }
//
//    public void dfs(Node cur) {
//        if (cur == null) {
//            return;
//        }
//        dfs(cur.left);
//        if (pre != null) {
//            pre.right = cur;
//        } else {
//            head = cur;
//        }
//        cur.left = pre;
//        pre = cur;
//        dfs(cur.right);
//    }
//}
//
//public class Test1 {
//}
